#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


bool findPath(const vector<string> &input, vector<vector<bool> > &visited, const string &str, int index, int x, int y)
{
    if (index == str.size()) 
        return true;
    if (x < 0 || x >= input.size() | y < 0 || y >= input[0].size()) return false;
    if (visited[x][y]) return false;

    if (input[x][y] == str[index]) {
        visited[x][y] = true;        
        if (findPath(input, visited, str, index+1, x-1, y)) return true; 
        if (findPath(input, visited, str, index+1, x+1, y)) return true; 
        if (findPath(input, visited, str, index+1, x, y-1)) return true; 
        if (findPath(input, visited, str, index+1, x, y+1)) return true; 
        visited[x][y] = false; 
    }
    return false;
}

int main(int argc, char **argv)
{
    vector<string> input;
    input.push_back("ABCE");
    input.push_back("SFCS");
    input.push_back("ADEE");
    vector<vector<bool> > visited(input.size(), vector<bool>(input[0].size(), false));
    string target = "ABCED";
    for (int i = 0; i < input.size(); i++) {
        for (int j = 0; j < input[0].size(); j++) {
            if (findPath(input, visited, target, 0, i, j))
                cout << "Find the target" << i << " " << j << endl;
        }
    }
    cout << "Could not find Target" << endl;
    return 0;
}
